# TLE 110/131

import copy
from collections import Counter
from typing import List

from sortedcontainers import SortedDict


class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        ans = []

        # ---------- 处理数组中存在的0的情况 ----------
        # 判断是否存在0：如果有1个0，则所有值必然有2个相同的；如果有2个0，则所有值必然有4个相同的……
        count = Counter(sums)
        num0 = num1 = min(count.values())
        while num1 % 2 == 0:
            ans.append(0)
            n -= 1
            num1 //= 2

        # 数组中只有0的情况
        if n == 0:
            return ans

        # 清理数组中因0产生的重复值
        sums = []
        for k, v in count.items():
            sums.extend([k] * (v // num0))

        # ---------- 处理数组中非0数的情况 ----------
        # print(n, ans, sums)

        # 当前最大值为所有正数的和
        max_val = max(sums)

        # 当前最小值为所有负数的和
        min_val = min(sums)

        # 统计所有可能存在的数绝对值
        set_sums = set(sums)
        choice = sorted(set([abs(s) for s in sums if s != 0]))
        # print(choice)

        count0 = SortedDict(Counter(sums))

        abs_list = []

        i = 0
        while i < len(choice):
            now = choice[i]

            # 判断当前绝对值是否存在
            find = True
            count1 = copy.deepcopy(count0)
            for k in count1:
                if count1[k] > 0:
                    if k + now not in count1 or count1[k + now] < count1[k]:
                        find = False
                        break
                    count1[k + now] -= count1[k]

            # 包含当前绝对值
            if find:
                abs_list.append(now)
                count0 = {k: v for k, v in count1.items() if v > 0}
            else:
                i += 1

            # print(now, ":", abs_list, count0)

            # 如果只剩下一个数，则结束
            if len(count0) == 1:
                break

        # print("绝对值列表:", abs_list, min_val, max_val)

        # 只有正数或只有负数的情况
        if min_val >= 0:
            return ans + abs_list
        if max_val <= 0:
            return ans + [-v for v in abs_list]

        # 回溯寻找最终解
        res = []
        left_lst = []
        right_lst = []

        def dfs(i, left, right):
            if i == len(abs_list):
                if left == 0 and right == 0:
                    res.append([-v for v in left_lst] + [v for v in right_lst])
                return

            if abs_list[i] <= -left:
                left_lst.append(abs_list[i])
                dfs(i + 1, left + abs_list[i], right)
                left_lst.pop()
            if res:
                return

            if abs_list[i] <= right:
                right_lst.append(abs_list[i])
                dfs(i + 1, left, right - abs_list[i])
                right_lst.pop()

        dfs(0, min_val, max_val)

        return ans + res[0]


if __name__ == "__main__":
    print(Solution().recoverArray(n=3, sums=[-3, -2, -1, 0, 0, 1, 2, 3]))  # [1,2,-3]
    print(Solution().recoverArray(n=2, sums=[0, 0, 0, 0]))  # [0,0]
    print(Solution().recoverArray(n=4, sums=[0, 0, 5, 5, 4, -1, 4, 9, 9, -1, 4, 3, 4, 8, 3, 8]))  # [0,-1,4,5]
